/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/integer-to-roman
   @Language: C++
   @Datetime: 17-04-15 11:15
   */

class Solution {
public:
	/**
	 * @param n The integer
	 * @return Roman representation
	 * Tip: See http://baike.baidu.com/view/42061.htm
	 */
	string intToRoman(int n) {
		// Write your code here
		vector<int> num = {1000,900,500,400,100,90
			,50,40,10,9,5,4,1};
		vector<string> roman={"M","CM","D","CD","C","XC"
			,"L","XL","X","IX","V","IV","I"};
		string ans;
		for(int i=0; i<num.size(); ++i)
			for(int r=n/num[i]; r--; n-=num[i])
				ans.append(roman[i]);
		return ans;
	}
};
